package algorithm.bfprt;

public class FindMinKth {

    //O(N)
    public static int findMinKth(int[] arr, int k){
        int process = process(arr, 0, arr.length - 1, k - 1);
        return process;
    }

    public static int process(int[] arr, int L, int R, int k){
        if(L == R){
            return arr[L];
        }
        swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
        int[] partition = partition(arr, L, R);
        if(partition[0] <= k && partition[1] >= k)
            return arr[k];
        else if(partition[0] > k)
            return process(arr, L, partition[0] - 1, k);
        else
            return process(arr, partition[1] + 1, R, k);
    }

    public static int[] partition(int[] arr, int L, int R){
        int[] result = new int[2];
        int index = L;
        int less = L - 1;
        int more = R;
        while(index != more){
            if(arr[index] > arr[R]){
                swap(arr, --more, index);
            }else if(arr[index] == arr[R]){
                index++;
            }else {
                swap(arr, index++, ++less);
            }
        }
        swap(arr, index, R);
        result[0] = less + 1;
        result[1] = index;
        return result;
    }

    public static void swap(int[] arr, int a, int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }

    public static int findMinKth2(int[] arr, int k){
        int process = bfprt(arr, 0, arr.length - 1, k - 1);
        return process;
    }

    //T(N) = O(N) + T(N/5) + T(7N/10) ==> O(N)
    public static int bfprt(int[] arr, int left, int right, int k){
        if(left == right)
            return arr[left];
        //获取中位数数组的中位数
        int median = medianOfMedians(arr, left, right);//O(N) + T(N/5)
        int[] partition2 = partition2(arr, left, right, median);//O(N)
        //T(7N/10)
        if(partition2[0] <= k && partition2[1] >= k)
            return arr[k];
        else
            if(partition2[0] > k)
                return bfprt(arr, left, partition2[0] - 1, k);
            else
                return bfprt(arr, partition2[1] + 1, right, k);
    }

    public static int medianOfMedians(int[] arr, int left, int right){
        int num = (right - left) % 5 == 0? (right - left) / 5 : (right - left) / 5 + 1;
        int[] medians = new int[num];
        for (int i = 0; i < medians.length; i++) {
            int part_left = left + i * 5;
            int part_right = Math.min(part_left + 4, right);
            medians[i] = getMedian(arr, part_left, part_right);
        }//O(N)
        return bfprt(medians, 0, num - 1, (num - 1) / 2);//T(N/5)
    }

    public static int getMedian(int[] arr, int left, int right){
        for (int index = left; index < right - left + 1; index++) {
            int tmp = arr[index];
            int i;
            for (i = index -1; i >= left && arr[i] > tmp; i--) {
                arr[i+ 1] = arr[i];
            }
            arr[i + 1] = tmp;
        }
        return arr[(right + left) / 2];
    }

    public static int[] partition2(int[] arr, int L, int R, int pivot){
        int[] result = new int[2];
        int index = L;
        int less = L - 1;
        int more = R + 1;
        while(index != more){
            if(arr[index] > pivot){
                swap(arr, --more, index);
            }else if(arr[index] == pivot){
                index++;
            }else {
                swap(arr, index++, ++less);
            }
        }
        result[0] = less + 1;
        result[1] = index - 1;
        return result;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxSize) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 1000000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int k = (int) (Math.random() * arr.length) + 1;
            int ans1 = findMinKth(arr, k);
            int ans2 = findMinKth2(arr, k);
            if (ans1 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

}
